An algebraic codebook, which algebraically arranges a small number of pulses to form a fixed codebook vector, does not require a memory for a codebook and makes it possible to reduce the amount of computation by codebook search in a relatively easy manner, and, consequently, is adopted for various standard codec including G.729 in ITU-T for speech coding.
However, an algebraic codebook merely arranges a small number of pulses algebraically, and, consequently, there is a limit to the vector characteristics that can be expressed by the algebraic codebook. As a result, the algebraic codebook does not always yield sufficient coding quality. Here, as a technique of improving an algebraic codebook, there is a technique referred to as “pulse dispersion” (e.g., see Patent Document 1). By convoluting pulses with a specific shape of dispersion vectors, this technique makes it possible to generate vectors having characteristics that are difficult to be expressed by a sparse pulse vector generated in an algebraic codebook.
Here, the amount of computation in an algebraic codebook search increases when the number of pulses to be used increases. Consequently, ingenuity is required to reduce the amount of computation especially when an algebraic codebook with a large number of pulses is used. For example, when the number of pulses increases like ten pulses, the number of combinations is enormous, and, consequently, it is not practical to perform exhaust codebook search. To reduce the amount of computation in this algebraic codebook with a large number of pulses, there is a technique of limiting the range of codebook search by combining an evaluation function that minimizes errors in the synthesized signal and an evaluation function that minimizes errors in the linear prediction residual signal (e.g., see Patent Document 2).
According to this technique, upon a general algebraic codebook search, to minimize errors in the synthesized signal, evaluation function Es expressed by following equation 1 is maximized.
                    (                  Equation          ⁢                                          ⁢          1                )                                                                      E          s                =                                            (                                                x                  t                                ⁢                Hc                            )                        2                                              c              t                        ⁢                          H              t                        ⁢            Hc                                              [        1        ]            
Here, “x” is the target vector, “H” is the lower triangular matrix expressing impulse response convolution in an auditory weighting synthesis filter, “c” is the sparse pulse vector generated by an algebraic codebook, and subscript “t” shows that the matrix (or vector) is a transposed matrix (or transposed vector). For example, G.729 in ITU-T performs a codebook search based on the above-noted evaluation equation.    Patent Document 1: Japanese Patent Application Laid-Open No. Hei 10-63300    Patent Document 2: Published Japanese Translations of PCT International Publication for patent applications Laid-Open No. Hei 10-513571